
// 线性表的顺序存储和链式存储

#include "stdlib.h"
#include "stdio.h"
typedef int elemtype;
#define MAXSIZE 100 //线性表允许的最大长度
typedef struct      //定义线性表的结构
{
    elemtype data[MAXSIZE]; //表示线性表（a1，a2，….,an）
    int length;             //length表示线性表的实际长度
} SeqList;

// 线性表的初始化
SeqList *Init_List()
{
    SeqList *L = (SeqList *)malloc(sizeof(SeqList));
    if (!L)
    {
        return NULL;
    }
    else
    {
        L->length = 0;
        return L;
    }
    return L;
}

//  线性表赋值
void AssignSeqList(SeqList *L)
{
    int i;
    printf("请输入元素个数:\n");
    scanf("%d", &L->length);
    if (L->length >= MAXSIZE)
    {
        printf("个数溢出,无法完成赋值\n");
    }
    printf("请按照元素个数依次输入元素值:\n");
    for (i = 0; i < L->length; i++)
    {
        scanf("%d", &L->data[i]);
    }
}

// 输出线性表
void OutputSeqList(SeqList *L)
{
    int i;
    printf("线性表的长度是%d\n", L->length);
    printf("顺序表的元素依次是:\n");
    for (i = 0; i < L->length; i++)
    {
        printf("%d\t", L->data[i]);
    }
    printf("\n");
}

// 线性表的插入操作
int InsertSeqList(SeqList *L, int i, elemtype x)
{
    if (i > L->length)
    {
        printf("无法插入\n");
        return 0;
    }
    // 插入后的数据整体后移;
    int count, temp;
    count = L->length;
    for (count; count >= i; count--)
    {
        temp = L->data[count - 1];
        L->data[count] = temp;
    }
    L->data[i - 1] = x;
    L->length++;
    printf("\n");
    return 1;
}

// 线性表删除操作
/**
 * i 要删除元素的序号(不是第几个) ,即是要删除的元素下标
 */
int DeleteSeqList(SeqList *L, int i)
{

    int count, temp;
    // 删除后数据整体前移
    for (i; i < L->length; i++)
    {
        L->data[i] = L->data[i + 1];
    }
    L->length--;
    return 1;
}

// 线性表按值查找
/**
 * x,要查找的元素,有返回下标,无该值返回-1
 */
int Locate_SeqList(SeqList *L, int x)
{
    int value, flag;
    for (int i = 0; i < L->length; i++)
    {
        if (L->data[i] == x)
        {
            value = i;
            flag = 1;
            break;
        }
    }

    if (flag)
    {
        printf("找到了,%d的下标是%d\n", x, value);
        return value;
    }
    else
    {
        printf("线性表中找不到%d\n", x);
    }
    return -1;
}

int main()
{
    SeqList *L;
    int k, i, x;
    do
    {
        printf("\n\n\n\n");
        printf("\t\t\t 链表子系统\n");
        printf("\t\t*******************************\n");
        printf("\t\t*        1----初 始 化  　　　*\n");
        printf("\t\t*        2----赋    值　　　　*\n");
        printf("\t\t*        3----插　　入　　　　*\n");
        printf("\t\t*        4----删　　除　　　　*\n");
        printf("\t\t*        5----查　　找　　　　*\n");
        printf("\t\t*        6----显　　示　　　　*\n");
        printf("\t\t*        0----返　　回　　　　*\n");
        printf("\t\t*******************************\n");
        printf("\t\t 请选择菜单项(0－6)：");
        scanf("%d", &k); //getchar();
        switch (k)
        {
        case 1:
            L = Init_List();
            if (L == NULL)
                printf("初始化顺序表失败\n");
            else
                printf("初始化顺序表成功\n");
            break;
        case 2:
            AssignSeqList(L);
            OutputSeqList(L);
            break;
        case 3:
            printf("请输入插入位置和插入数据：");
            scanf("%d%d", &i, &x);
            k = InsertSeqList(L, i, x);
            if (k == 1)
            {
                printf("插入操作成功！插入元素后顺序表如下\n");
                OutputSeqList(L);
            }
            else
                printf("插入操作失败\n");
            break;
        case 4:
            printf("请输入删除元素的位置：");
            scanf("%d", &i);
            k = DeleteSeqList(L, i-1);
            if (k == 1)
            {
                printf("删除操作成功，删除元素后顺序表如下\n");
                OutputSeqList(L);
            }
            else
                printf("删除操作失败\n");
            break;
        case 5:
            printf("请输入要查找的数值x:");
            scanf("%d", &x);
            i = Locate_SeqList(L, x);
            if (i != -1)
            {
                OutputSeqList(L);
                printf("线性表中值为%d所在的位置是%d\n", x, i+1);
            }
            else
            {
                printf("线性表中无此元素!!\n");
            }
            break;
        case 6:
            OutputSeqList(L);
            break;
        }
    } while (k != 0);
    system("pause");
    return 0;
}